0959. 由斜杠划分区域【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 并查集

1. 📝 题目描述

• leetcode

在由 1 x 1 方格组成的 n x n 网格 grid 中，每个 1 x 1 方块由 '/'、'\' 或空格构成。这些字符会将方块划分为一些共边的区域。

给定网格 grid 表示为一个字符串数组，返回 区域的数量。

请注意，反斜杠字符是转义的，因此 '\' 用 '\\' 表示。

---

示例 1：

输入：grid = [" /","/ "]
输出：2

示例 2：

输入：grid = [" /","  "]
输出：1

示例 3：

输入：grid = ["/\\","\\/"]
输出：5
解释：回想一下，因为 \ 字符是转义的，所以 "/\\" 表示 /\，而 "\\/" 表示 \/。

---

提示：

• n == grid.length == grid[i].length
• 1 <= n <= 30
• grid[i][j] 是 '/'、'\'、或 ' '

2. 🎯 s.1 - 并查集

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {string[]} grid
 * @return {number}
 */
var regionsBySlashes = function (grid) {
  const n = grid.length
  const parent = new Array(n * n * 4).fill(0).map((_, i) => i)

  const find = (x) => {
    if (parent[x] !== x) parent[x] = find(parent[x])
    return parent[x]
  }

  const union = (x, y) => {
    parent[find(x)] = find(y)
  }

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      const base = (i * n + j) * 4
      const ch = grid[i][j]

      // 格内连接
      if (ch === '/') {
        union(base + 0, base + 3) // 上 - 左
        union(base + 1, base + 2) // 右 - 下
      } else if (ch === '\\') {
        union(base + 0, base + 1) // 上 - 右
        union(base + 2, base + 3) // 下 - 左
      } else {
        union(base + 0, base + 1)
        union(base + 1, base + 2)
        union(base + 2, base + 3)
      }

      // 相邻格连接
      if (i > 0) union(base + 0, ((i - 1) * n + j) * 4 + 2)
      if (j > 0) union(base + 3, (i * n + j - 1) * 4 + 1)
    }
  }

  let regions = 0
  for (let i = 0; i < n * n * 4; i++) {
    if (find(i) === i) regions++
  }

  return regions
}

• 时间复杂度：$O(n^2\times \alpha (n^2))$，其中 n 是网格边长
• 空间复杂度：$O(n^2)$，并查集数组

算法思路：

• 将每个 $1\times 1$ 格子拆分为 4 个三角形区域：上(0)、右(1)、下(2)、左(3)
• 根据字符决定格内连接：/ 连接上左和右下，\\ 连接上右和下左，空格连接全部
• 相邻格子连接：当前格的上部与上方格的下部相连，当前格的左部与左方格的右部相连
• 最终统计连通分量数即为区域数